/**
* @description: 81. 搜索旋转排序数组 II
* @author hewei
* @date 2022/7/26 16:17
* @version 1.0
*/

public class Search2 {

    public static void main(String[] args) {
        Search2 search2 = new Search2();
        int[] nums = {1,0,1,1,1};
        System.out.println(search2.search(nums, 0));
    }

    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] == target) return true;
            if (nums[mid] == nums[l] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } else if (nums[mid] >= nums[l]) {
                if (target >= nums[l] && target <= nums[mid]) {
                    r = mid - 1;
                } else l = mid + 1;
            } else {
                if (target >= nums[mid] && target <= nums[r]) {
                    l = mid + 1;
                } else r = mid - 1;
            }
        }
        return false;
    }
}
